package s12_经典算法.a3_KMP算法;

/**
 * Created by 西瓜瓜
 * Date :2022/2/27
 * Description :
 * Version :1.0
 * <p>
 * KMP算法
 */
public class KMPAlgorithm {

    public static void main(String[] args) {
        String str1 = "dabsvgsabklgjsakbkesagjsabrkgbksabask f kasdgfhsakuhfkl;as efl;hsa klegbsabkvl assaeufhsaef as";
        String str2 = "saef as";
        System.out.println(new KMPAlgorithm().kmpalgorithm(str1, str2));
    }


    /**
     * KMP匹配算法实现
     *
     * @param str1 原始字符串
     * @param str2 待匹配字符串
     * @return
     */
    public int kmpalgorithm(String str1, String str2) {
        // 获取子串的部分匹配值表
        int[] arr = kmpNext(str2);

        for (int i = 0, j = 0; i < str1.length(); i++) {

            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = arr[j - 1];
            }

            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }

            if (j == str2.length()) {
                return i - j + 1;
            }


        }

        return -1;
    }

    /**
     * 获取子串的部分匹配值表
     *
     * @param dest 子串
     * @return
     */
    public int[] kmpNext(String dest) {
        int[] arr = new int[dest.length()];
        // 如果字符串长度是1，部分匹配值就是0；
        arr[0] = 0;

        for (int i = 1, j = 0; i < dest.length(); i++) {

            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = arr[j - 1];
            }
            // 条件满足时，部分匹配值+1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            arr[i] = j;
        }
        return arr;
    }

}
